import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class IterativeLengthening implements Search {
	
	private Graph graph = null;
	private Node node = null;
	private List<Node> visited;
	private int count = 0;
	private int iterations = 1;
	public Node solve(String start, String end){
		int pathCostLimit = 1;
		int minPathCost;
		boolean solution = false;
		if(graph != null){
			while(!solution){
				Graph initial = new Graph(graph);
				minPathCost = 99999;
				Node root = initial.getFirstNode(start);
				List<Node> L = new ArrayList<Node>();
				visited = new ArrayList<Node>();
				
				L.add(root);
				
				while(true){
					if(L.isEmpty() && minPathCost == 99999){
						return null;
					}
					
					if(L.isEmpty() && minPathCost != 99999){
						pathCostLimit = minPathCost;
						break;
					}
					
					/**
					 *  For DFS: L.remove(L.size()-1) and Collections.reverse(children);
					 */
					visited.add(node = L.remove(0));
					node.setVisited(true);
					count++;
					if(node.getContent().equals(end)){
						return node;
					} else {
						List<Node> children = initial.getNeighbours(node);
//						Collections.reverse(children);
						for(Node child : children){
							if(!child.isVisited()) {
								child.setCost(child.getCost() + child.getParent().getCost());

								if(child.getCost() <= pathCostLimit){
									L.add(child);
								} else {
									minPathCost = Math.min(child.getCost(), minPathCost);
								}
							}
						}
					}
				}
				setIterations(getIterations() + 1);
			}
		}
			
		
		
		return null;
	}
	
	public Graph getGraph() {
		return graph;
	}


	public void setGraph(Graph graph) {
		this.graph = graph;
	}


	public List<Node> getVisited() {
		return visited;
	}


	public void setVisited(List<Node> visited) {
		this.visited = visited;
	}

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}

	public int getIterations() {
		return iterations;
	}

	public void setIterations(int iterations) {
		this.iterations = iterations;
	}
}
